package leetcode

// https://leetcode.com/problems/find-all-anagrams-in-a-string/
func findAnagrams(s string, p string) []int {
	res := make([]int, 0)
	need, window, validate := make(map[rune]int), make(map[rune]int), 0
	left, right := 0, 0
	for _, c := range p {
		need[c] = need[c] + 1
	}

	for ; right < len(s); right++ {
		c := rune(s[right])
		window[c] = window[c] + 1
		if need[c] == window[c] {
			validate += 1
		}
		// shrink
		for right-left+1 >= len(p) {
			if validate == len(need) {
				res = append(res, left)
			}
			lc := rune(s[left])
			if need[lc] == window[lc] {
				validate--
			}
			window[lc] -= 1
			left++
		}
	}
	return res
}
